package LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class _226_翻转二叉树 {
	// 前序遍历方式翻转
//	 public TreeNode invertTree(TreeNode root) {
//		 if (root == null) {
//			return root;
//		}
//		 
//	     TreeNode tmp = root.left;
//	     root.left = root.right;
//	     root.right = tmp;
//
//	     invertTree(root.left);
//	     invertTree(root.right);
//		 return root;   
//	 }
	 
		
	 // 后序遍历方式翻转
//	public TreeNode invertTree(TreeNode root) {
//		if (root == null) {
//			return root;
//		}
//		invertTree(root.left);
//		invertTree(root.right);
//
//		TreeNode tmp = root.left;
//		root.left = root.right;
//		root.right = tmp;
//
//		return root;   
//	}
	
	 // 中序遍历方式翻转
//	public TreeNode invertTree(TreeNode root) {
//		if (root == null) {
//			return root;
//		}
//		invertTree(root.left);
//		
//		TreeNode tmp = root.left;
//		root.left = root.right;
//		root.right = tmp;
//		// 已经讲左子树翻转为右子树,所以现在要取左子树就是原来的右子树
//		invertTree(root.left);
//		
//		return root;   
//	}
	
	 // 层序遍历方式翻转
	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return root;
		}
		
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			
			TreeNode tmp = node.left;
			node.left = node.right;
			node.right = tmp;
			
			if (node.left != null) {
				queue.offer(node.left);
			}
			
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		
		return root;   
	}
}
